Thực đơn
Bài toán vận tải Giải thuậtGiải thuật giải bài toán vận tải cũng là thuật toán đơn hình. Nó xuất phát từ việc chọn phương án đầu tiên rồi cải tiến dần cho đến khi đạt tối ưu.
Có một số phương pháp tìm phương án ban đầu.
Phương pháp này trước hết phân phối lượng hàng lớn nhất có thể được vào ô dầu tiên ở góc tây-bắc, nghĩa là ô (1,1), bằng cách đặt x 11 = m i n ( a 1 , b 1 ) {\displaystyle x_{11}=min(a_{1},b_{1})} . Khi đó, hoặc điểm phát A 1 {\displaystyle A_{1}} hết hàng, hoặc điểm thu B 1 {\displaystyle B_{1}} hết nhu cầu, ta có thể loại điểm phát A 1 {\displaystyle A_{1}} hoặc điểm B 1 {\displaystyle B_{1}} ra khỏi bảng, rối lại tiếp tục phân phối cho ô tây bắc trong phần còn lại của bảng.
Với ví dụ cho ở trên ta có
Phương án đầu tiên lập theo quy tắc góc tây bắcCác số nhỏ ghi ở góc trên mỗi ô là cước phí vận chuyển mỗi đơn vị hàng hoá từ điểm phát thứ i đến điểm thu thứ j.
Khi đó tổng chi phí vận chuyển cho phương án này là:
3×50+5×100+1×50+3×150+4×50+2×50=1450Đây chưa phải là phương án tối ưu.
Ta cũng lần lượt phân phối vào các ô như trên nhưng tiêu chuẩn ưu tiên là cước phí nhỏ nhất trong những ô còn có thể phân phối.
Trong ví dụ trên
Phương án đầu tiên lập theo quy tắc ưu tiên cước phí nhỏ nhấtTổng chi phí vận chuyển theo phương án này là:
3×50+2×100+1×150+3×100+7×50=1150Sau khi dùng một trong các phương pháp lập phương án ban đầu (ngoài hai phương pháp trên còn có một số phương pháp khác), trong các phương án nhận được ta được một số ô (i, j) có giá trị x i , j > 0 {\displaystyle x_{i,j}>0} , các ô đó được gọi là các ô chọn một số ô khác có x i , j = 0 {\displaystyle x_{i,j}=0} được gọi là các ô tự do. Nếu viết lại hệ ràng buộc của bài toán vận tải như với bài toán quy hoạch tuyến tính tổng quát, các ô chọn trong các phương án ban đầu ứng với các ẩn cơ sở. Nếu phương án là không suy biến thì các ô tự do đều ứng với các ẩn tự do, nếu phương án là suy biến có thể có những ô tự do ứng với các ẩn cơ sở. Khi viết bài toán vận tải dưới dạng bài toán QHTT tổng quát, với điều kiện cân bằng cung cầu, hạng của hệ ràng buộc của BTVT m điểm phát, n điểm thu là r=m+n-1. Do vậy khi không suy biến một phương án (cơ sở) tạo ra từ một trong các phương pháp trên có đúng m+n-1 ô chọn là ô cơ sở, các ô còn lại là ô tự do.
Ta xem xét việc điều chỉnh một phương án cơ sở sẽ mang lại "lợi" hay "hại" cho giá thành vận chuyển.Giả sử trong một điều chỉnh nào đó một ô tự do ( i 0 , j 0 ) {\displaystyle (i_{0},j_{0})} được tăng thêm một lượng hàng h. Khi đó trong dòng i 0 {\displaystyle i_{0}} phải có một ô ( i 0 , j 1 ) {\displaystyle (i_{0},j_{1})} nào đó giảm đi lượng h để tổng hàng hoá trong dòng không đổi, tiếp theo, hàng trong cột j 1 {\displaystyle j_{1}} giảm đi tại ( i 0 , j 1 ) {\displaystyle (i_{0},j_{1})} thì phải tăng trong cùng cột j 1 {\displaystyle j_{1}} tại dòng i 1 {\displaystyle i_{1}} cùng cột ngiã là tại ô ( i 1 , j 1 ) {\displaystyle (i_{1},j_{1})} ,... sau một số hữu hạn bước, mỗi bước chuyển từ đi theo hàng sang đi theo cột ta quay về gặp ô cùng cột với ô đầu tiên, ô ( i k , j 0 ) {\displaystyle (i_{k},j_{0})} để giảm lượng hàng ở đó đi một lượng đúng bằng h, nghĩa là ta có một chu trình.
Định nghĩa
Ví dụ hai chu trình trong bảng vận tải, mỗi chu trình là một đường đi khép kín luôn rẽ một góc vuông tại mỗi bước của nó, những ô nằm trên đường thẳng mà nó đi qua không nằm trong chu trìnhMột chu trình trong bảng vận tải là một dãy các ô trong đó ô đầu tiên và ô thứ hai nằm trên cùng một dòng, hai ô liên tiếp hoặc nằm trên cùng một dòng, hoặc cùng nằm trên một cột, ba ô liên tiếp không nằm trên cùng một hàng hoặc một cột, ô đầu tiên và ô cuối cùng nằm trên cùng một cột.Có thể viết dãy các ô trong chu trình như sau
( i 0 , j 0 ) , ( i 0 , j 1 ) , ( i 1 , j 1 ) , ( i 1 , j 2 ) , . . . , ( i k , j 0 ) {\displaystyle (i_{0},\;j_{0}),(i_{0},\;j_{1}),(i_{1},\;j_{1}),(i_{1},\;j_{2}),...,(i_{k},\;j_{0})}Có thể hình dung chu trình là một đường đi khép kín qua các ô của bảng vận tải trong đó cứ mỗi lần qua một ô nó lại rẽ một góc 90 0 {\displaystyle 90^{0}} .
Tính chất
Phương án cơ sở của BTVT là tối ưu khi và chỉ khi nó không có ô tự do với giá trị âm.
Phương pháp thế vị tính giá của ô tự do
Giá của các ô tự do có thể tính nhờ phương pháp thế vị như sau:
Đưa thêm m+n ẩn p 1 , p 2 , . . . , p m {\displaystyle p_{1},\;p_{2}\;,...,\;p_{m}} và q 1 , q 2 , . . . , q n {\displaystyle q_{1},\;q_{2}\;,...,\;q_{n}} .
Hệ m+n-1 phương trình p i + q j = c i , j {\displaystyle p_{i}+q_{j}=c_{i,j}} với m+n-1 ô cơ sở có thể giải dễ dàng nhờ cho một ẩn, chẳng hạn p 1 = 0 {\displaystyle p_{1}=0} .Khi đó giá của các ô tự do (i, j) được tính bằng công thức v i , i = p i + q j {\displaystyle v_{i,i}=p_{i}+q_{j}} .
Thực đơn
Bài toán vận tải Giải thuậtLiên quan
Bài Tiến lên Bài toán người bán hàng Bài toán 3 vật thể Bài hát hay nhất Bài hát hay nhất (mùa 1) Bài hát hay nhất (mùa 3) Bài hát hay nhất (mùa 2) Bài ngoại và phân biệt chủng tộc liên quan đến đại dịch COVID-19 Bài tấn Bài ca hy vọngTài liệu tham khảo
WikiPedia: Bài toán vận tải